//
// Created by 高森森 on 2022/2/12.
//

#ifndef LEETCODE_SOLUTION37UNI_H
#define LEETCODE_SOLUTION37UNI_H
#include<iostream>
#include<vector>
#include <numeric>

using namespace std;
class UnionFind{
public:
    vector<int>father;//父亲节点
    vector<int>rank;//秩的数
    int n;//节点个数
    int setCount;//连通分量数
public:
    //查询父结点
    UnionFind(int _n):n(_n),setCount(_n),rank(_n,1),father(_n){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
   int find(int x,vector<int>&father){
       if(x==father[x])
           return x;
       else{
           father[x]=find(father[x],father);
           return father[x];
       }
   }

   //并查集合并
   bool merge(int i,int j){
        int x=find(i,father);
        int y=find(j,father);
        if(x==y){
            return false;
        }
        if(rank[x]<=rank[y]){
            father[x]=y;
        }
        else{
            father[y]=x;
        }
        if(rank[x]==rank[y]&&x!=y)
            rank[y]++;
        setCount--;
        return true;
    }
    bool isConnected(int x,int y){
        x=find(x,father);
        y=find(y,father);
        return x==y;
    }
};
class Solution37uni {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        //让序号可以从0开始 注意这里必须用引用，否则无法修改edge的值
        for(auto &edge:edges){
            edge[1]--;
            edge[2]--;
        }
        UnionFind a(n);
        UnionFind b(n);
        int ans=0;
        //先添加公共边 注意如果添加公共边时发现两点已经连通了
        //那么这条边就是不必要的，可以删除，同时a和b都需要复制相同的并查集
        //所以如果可以删除，ans++,b只需要做相同的操作，不需要在ans++了；
        for(auto &edge:edges){
            if(edge[0]==3){
                if(!a.merge(edge[1],edge[2])){
                    ans++;
                }
                //如果公共边成功添加，那么在b的并查集里也需要添加
                else{
                    b.merge(edge[1],edge[2]);
                }
            }
        }
        for(auto &edge:edges){
            if(edge[0]==1){
                if(!a.merge(edge[1],edge[2])){
                    ans++;
                }
            }
            else if(edge[0]==2){
                if(!b.merge(edge[1],edge[2])){
                    ans++;
                }
            }
            }
        if(a.setCount!=1||b.setCount!=1)
        {
            return -1;
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION37UNI_H
